Counter
A lot of interview problems boil down to one question: how many times does each thing show up? Anagram checks, frequency problems, "find the most common element", these all need a count of every item in a collection.
You could build that count yourself with a plain dict and a loop, but Python's collections module already has a purpose-built tool for this: Counter. It is a dict subclass, so everything you already know about dicts still applies. It just adds a few defaults and methods that make counting less annoying to write.
Counting occurrences of each element
O(n)Pass any iterable to Counter() and it counts every element for you. Here it is on a list:
A string is also an iterable of characters, so the same call counts letters:
Note
Do not read anything into the order these print in. Counter is a dict, and exactly how its keys print depends on the Python implementation, insertion order, count order, or something else. If you need a specific order, like highest count first, ask for it explicitly with most_common(), covered next.
most_common() and how ties break
O(n log n)most_common() gives you that same highest-to-lowest order as a list of tuples, which is usually more useful than the Counter object itself. Pass a number to get only the top few:
Note
How ties break: "cat" and "dog" both show up twice, and "cat" comes first in the result because it was counted first. Insertion order is the tiebreaker, not alphabetical order or anything else. This matters if an interviewer asks for "the most common element" and there are multiple valid answers.
Counter vs a plain dict
O(1)The biggest practical difference: looking up a key that was never counted returns 0 from a Counter, instead of raising an error.
Do the same lookup on a plain dict and you get a KeyError instead:
Note
This is why counts[item] += 1 works on the very first time you see item, with a Counter. With a plain dict, that same line raises a KeyError unless you check item in d or use d.get(item, 0) first.
Counter arithmetic (+, -, &, |)
O(n + m)Two counters can be combined directly. + adds counts, - subtracts them, & keeps the smaller count for each shared key, and | keeps the larger:
Note
The gotcha: all four operators silently drop any key whose result is zero or negative. Above, c starts at 0 in a and d starts at 0 in b, and neither ever appears in a subtraction or intersection result. a - b drops b and c entirely because their subtracted counts are negative, it does not keep them at 0. If you need to preserve zero or negative counts, work with the underlying dicts directly instead of these operators.
Converting a Counter
A Counter is a dict, so dict() and .items() work on it the same way they do on any dict:
Note
dict() and .items() reflect a Counter's insertion order ("a" first, seen first). That is not the same as the sorted-by-count order most_common() gives you. Do not assume a converted Counter is sorted by count.
elements() does the opposite of counting: it expands the counts back into a stream of individual items, in insertion order, skipping any key with a zero or negative count.
Where Counter shows up in interviews
Any time a problem is really asking "count these, then compare the counts", reach for Counter before writing a manual loop. The two shapes that come up over and over:
- Anagram checks. Two strings are anagrams if
Counter(s1) == Counter(s2). Counter objects support==directly, so there is no need to sort either string first. See Permutation in String for a sliding-window version of this idea. - Frequency-window problems. Problems that slide a window across a string or list and ask "does this window's letter counts match a target" almost always keep a
Counterfor the window and compare it against a targetCounter. See Minimum Window Substring and Longest Repeating Character Replacement for two versions of that pattern.